package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/6/11 9:56
 */
public class DailyTemperatures {
    /**
     * 根据每日 气温 列表，请重新生成一个列表，
     * 对应位置的输出是需要再等待多久温度才会升高超过该日的天数。
     * 如果之后都不会升高，请在该位置用 0 来代替。
     * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
     * 你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]
     */
    @Test
    public void dailyTemperatures() {
        Assert.assertArrayEquals(new int[]{1, 1, 4, 2, 1, 1, 0, 0}, dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
        Assert.assertArrayEquals(new int[]{8, 1, 5, 4, 3, 2, 1, 1, 0, 0}, dailyTemperatures(new int[]{89, 62, 70, 58, 47, 47, 46, 76, 100, 70}));
        Assert.assertArrayEquals(new int[]{3, 1, 1, 2, 1, 1, 0, 1, 1, 0}, dailyTemperatures(new int[]{55, 38, 53, 81, 61, 93, 97, 32, 43, 78}));
        Assert.assertArrayEquals(new int[]{1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, dailyTemperatures(new int[]{34, 80, 80, 80, 34, 80, 80, 80, 34, 34}));
    }

    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        if (T.length == 0) {
            return res;
        }
        res[T.length - 1] = 0;
        if (T.length < 2) {
            return res;
        }
        for (int i = T.length - 2; i >= 0; i--) {
            if (T[i] < T[i + 1]) {
                res[i] = 1;
            } else if (res[i + 1] == 0 || i + 1 == T.length - 1) {
                res[i] = 0;
            } else if (T[i] == T[i + 1]) {
                res[i] = res[i + 1] + 1;
            } else {
                res[i] = res[i + 1] + 1;
                for (int j = i + res[i + 1] + 1; j <= T.length - 1; ) {
                    if (T[i] < T[j]) {
                        break;
                    } else if (res[j] == 0 || j == T.length - 1) {
                        res[i] = 0;
                        break;
                    } else if (T[i] == T[j]) {
                        res[i] = res[i] + res[j];
                        break;
                    } else {
                        res[i] = res[i] + res[j];
                        j = j + res[j];
                    }
                }
            }
        }
        return res;
    }

    public int[] dailyTemperatures2(int[] T) {
        int[] res = new int[T.length];
        if (T.length == 0) {
            return res;
        }
        res[T.length - 1] = 0;
        if (T.length < 2) {
            return res;
        }
        for (int i = T.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (T[i] < T[j]) {
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {
                    res[i] = 0;
                    break;
                }
                j = res[j] + j;
            }
        }
        return res;
    }
}
